package uestc.lj.basicPromotion.dfs;

/**
 * @Author:Crazlee
 * @Date:2021/11/28
 */
public class Code02_RobotWalk {
	/**
	 * 机器人走路问题
	 *
	 * @param n 一共有n格
	 * @param s 开始位置
	 * @param e 结束位置
	 * @param k 只能走k步
	 * @return 共有多少种走法
	 */
	public static int robotWalk1(int n, int s, int e, int k) {
		return process1(n, e, k, s);
	}

	/**
	 * @param N    共有n格
	 * @param end  结束位置
	 * @param left 还剩下多少步可以走
	 * @param cur  当前的位置
	 * @return
	 */
	private static int process1(int N, int end, int left, int cur) {
		// 终止条件，如果当前剩余步骤为0的情况下，如果到达了终点就返回一种走法。
		if (left == 0) {
			return cur == end ? 1 : 0;
		}
		if (cur == 1) {
			return process1(N, end, left - 1, 2);
		}
		if (cur == N) {
			return process1(N, end, left - 1, N - 1);
		}
		return process1(N, end, left - 1, cur - 1) + process1(N, end, left - 1, cur + 1);
	}

	//======================================================================================================

	/**
	 * 记忆化搜索优化
	 *
	 * @param n
	 * @param s
	 * @param e
	 * @param k
	 * @return
	 */
	public static int robotWalk2(int n, int s, int e, int k) {
		int[][] dp = new int[k + 1][n + 1];
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				dp[i][j] = -1;
			}
		}
		return process2(n, e, k, s, dp);

	}

	private static int process2(int N, int end, int left, int cur, int[][] dp) {
		// 先查看缓存中当前位置和剩余步骤是否有计算过，如果有直接返回。
		if (dp[left][cur] != -1) {
			return dp[left][cur];
		}
		// 终止条件，如果当前剩余步骤为0的情况下，如果到达了终点就返回一种走法。
		if (left == 0) {
			dp[left][cur] = cur == end ? 1 : 0;
			return dp[left][cur];
		}
		if (cur == 1) {
			dp[left][cur] = process1(N, end, left - 1, 2);
		} else if (cur == N) {
			dp[left][cur] = process1(N, end, left - 1, N - 1);
		} else {
			dp[left][cur] = process1(N, end, left - 1, cur - 1) + process1(N, end, left - 1, cur + 1);
		}
		return dp[left][cur];
	}

	//=======================================================================================================

	/**
	 * 动态规划优化
	 *
	 * @param N
	 * @param start
	 * @param end
	 * @param left
	 * @return
	 */
	public static int robotWalk3(int N, int start, int end, int left) {
		int[][] dp = new int[left + 1][N + 1];
		//将剩0步到达终点位置置为1
		dp[0][end] = 1;
		for (int i = 1; i <= left; i++) {
			for (int j = 1; j <= N; j++) {
				if (j == 1) {
					//只依赖其右上角
					dp[i][j] += dp[i - 1][2];
				} else if (j == N) {
					//只依赖其左上角
					dp[i][j] += dp[i - 1][N - 1];
				} else {
					//依赖其左上角和右上角
					dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j - 1];
				}
			}
		}
		//返回k步当前位置s的dp值
		return dp[left][start];
	}

	//=====================================================================================================

	/**
	 * 动态规划的优化使用一维数组
	 * @param N
	 * @param start
	 * @param left
	 * @param end
	 * @return
	 */
	public static int robotWalk4(int N, int start, int left, int end) {
		// 参数无效直接返回0
		if (N < 2 || left < 1 || start < 1 || start > N || end < 1 || end > N) {
			return 0;
		}

		int[] dp = new int[N + 1];
		dp[end] = 1;

		for (int i = 1; i <= left; i++) {
			// 左上角的值
			int leftUp = dp[1];
			for (int j = 1; j <= N; j++) {
				int tmp = dp[j];
				if (j == 1) {
					dp[j] = dp[j + 1];
				} else if (j == N) {
					dp[j] = leftUp;
				} else {
					dp[j] = leftUp + dp[j + 1];
				}
				leftUp = tmp;
			}
		}
		return dp[start];
	}
}
